package Leetcode.链表;

/**
 * @ClassName 奇偶链表
 * @since: 2023/8/17 16:06
 * @auth: kirito
 * @description:
 * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
 *
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
 *
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 *
 * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
 *
 * 思路：
 *  应该就是双指针 奇偶指针，每次走两，走到尽头后奇指针的next指向偶指针的head.
 **/
public class 奇偶链表 {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode a = head;
        ListNode b = head.next;
        ListNode c = b;
        while (b != null && b.next != null) {
            a.next = a.next.next;
            a = a.next;
            b.next = b.next.next;
            b = b.next;
        }
        a.next = c;
        return head;
    }
}
